1. Field of the Invention
The present invention relates to an estimation of a maximum likelihood sequence to be utilized in a digital communication receiver.
2. Description of the Background Art
In general, a digital communication receiver is required to recover the transmitted codes correctly from the received signals affected by the transmission distortion and the noises, by means of some signal processing.
One of the known method to achieve this correct recovery of the transmitted codes is the maximum likelihood sequence estimation using the Viterbi algorithm. In this method, when the received signal sequence is given, the transmission code sequence which makes the best matching with the received signal sequence is selected from all the conceivable transmission code sequence candidates. Here, the Viterbi algorithm is utilized in order to reduce the amount of calculations involved in this process.
This maximum likelihood sequence estimation assumes that the transmission path response is known in advance, while the transmission path response itself can be measured only when the transmission signals are known. In this respect, in the mobile radio communication such as an automobile telephone, the transmission path response constantly changes in time, so that it becomes necessary to carry out the transmission sequence estimation and the transmission path response estimation alternately and repeatedly, in order to follow such a constantly changing transmission path response. Such a procedure for the maximum likelihood sequence estimation has been called a transmission path adaptive maximum likelihood sequence estimation scheme, or more simply, an adaptive maximum likelihood sequence estimation scheme.
Conventionally, the following method has been known as an example of the adaptive maximum likelihood sequence estimation scheme capable of realizing a superior high speed follow up characteristic.
Namely, a conventional apparatus to be provided in a digital communication receiver for realizing this method has a configuration as shown in FIG. 1, which comprises: an input terminal 4 for entering a received baseband signal r(t); a sampling circuit 15 connected to the input terminal 4; a received signal memory 12 connected to the sampling circuit 15; a processing control unit 16 connected to the received signal memory 12; a matrix memory 11 connected to the processing control unit 16; and a path memory 13 connected to the processing control unit 16.
In this apparatus of FIG. 1, first, the received baseband signal r(t) entering at the input terminal 4 is sampled by a sampling circuit 15 at the sampling period equal to a transmission symbol period T. In the following, the time will be expressed in units of this transmission symbol period T, where k is an ordered number.
Also, the transmission path response is simulated by a transversal filter with a tap interval T and a tap number L, which is expressed by an L-dimensional vector h(k) defined by the following expression (1) in terms of a sequence of tap gains as elements. EQU h(k)=[h.sub.0, h.sub.1, . . . , h.sub.L-1 ].sup.t ( 1)
where .sup.t denotes the transpose.
In addition, each transmission code is assumed to be Q-valued, and a transmission signal vector s(k) comprising L symbols of such Q-valued transmission codes, a received signal vector r(k) comprising N samples of received signals corresponding to the transmission signal vector s(k), and a noise vector n(k) representing noise components in the received signal vector r(k) are defined by the following expressions (2) to (4), respectively. EQU s(k)=[s.sub.k, s.sub.k-1, . . . , s.sub.k-L+1 ].sup.t ( 2) EQU r(k)=[r.sub.k, r.sub.k-1, . . . , r.sub.k-N+1 ].sup.t ( 3) EQU n(k)=[n.sub.k, n.sub.k-1, . . . , n.sub.k-N+1 ].sup.t ( 4)
Furthermore, an N.times.L transmission signal matrix S(k) comprising N transmission signal vectors ranging from s.sup.t (k) to s.sup.t (k-N+1) is defined by the following expression (5). ##EQU1##
Then, the following transmission path equation (6) holds in this case. EQU r(k)=S(k) h(k)+n(k) (6)
Here, even when S(k) and r(k) are known in advance, n(k) cannot possibly be known in advance, so that the transmission path response h(k) cannot be derived from this equation (6) directly. On the other hand, however, it is possible to derive the transmission path response h(k) which minimizes an evaluation function E(k) defined by the following expression (7), directly from the above equation (6). ##EQU2## where .multidot. denotes the complex conjugate, and EQU e.sub.k+i =s.sup.t (k+i) h(k)-r.sub.k+i
In this case, the transmission path response h(k) which minimizes the above evaluation function E(k) can be expressed by the following expression (8). EQU h(k)=[S.sup..multidot.t (k) S(k)].sup.-1 S.sup..multidot.t (k) r(k)(8)
In the following, the estimation for the transmission path response h(k) derived by the expression (8) is called an estimated transmission path response.
In this manner, when the transmission signal sequence and the received signal sequence up to a certain time are given, the estimated transmission path response can be derived.
Now, a case of applying the Viterbi algorithm to a transmission code trellis with a number of states P and a number of branches per state Q as shown in FIG. 2 is considered, and the m-th state (1.ltoreq.m.ltoreq.P) at a time kT is denoted as m(k), while each state at each time is assumed to be equipped with a survivor path corresponding to a path metric p.sub.k,m and the estimated transmission path response h.sub.m (k).
Then, by considering a branch for making a transition from the state m'(k-1) to the state m(k) between the time (k-1)T and the time kT (which will be denoted as m(k)/m'(k-1) or m/m' hereinbelow), the estimated transmission path response h.sub.m' (k-1) at the state m'(k-1) can be expressed by the following expression (9). EQU h.sub.m' (k-1)=[S.sub.m'.sup..multidot.t (k-1) S.sub.m' (k-1)].sup.-1 S.sub.m '.sup..multidot.t (k-1) r(k-1) (9)
where r(k-1) can be read out from the received signal memory 12.
In this expression (9), a matrix G.sub.m' (k-1)=[S.sub.m'.sup..multidot.t (k-1) S.sub.m' (k-1)].sup.-1 S.sub.m'.sup..multidot.t (k-1) can be calculated as long as the code sequence {S.sub.k-N-L+1, . . . , S.sub.k-2, S.sub.k-1 } of the past (N+L-1) transmission symbols can be given in advance. Thus, by pre-calculating this matrix for all the possible code sequences of the length (N+L-1) and storing the pre-calculated matrices in the matrix memory 11 in advance, and then reading each one of them as the need arises, it is possible to reduce the amount of real time calculations.
Here, however, in this expression (9), a matrix [S.sub.m'.sup..multidot.t (k-1) S.sub.m' (k-1)] is not necessarily a normal one, and when this matrix is not normal, the calculation of the inverse of this matrix appearing in the above equation (9) is impossible. In such a case, conventionally, the estimated transmission path response in the state m'(k-1) has been approximated by the previous estimated transmission path response used at a previous time by the survivor path for that state m'(k-1) (i.e., the estimated transmission path response used in the state m"(k-2) in this case).
Namely, the estimated received signal r'.sub.k,m/m' (where suffix m/m' indicates that the quantity is related to the branch for making a transition from the state m' to the state m) at the state m(k) is obtained by the following equation (10), assuming the previous estimated transmission path response h.sub.m' (k-1) is still valid. EQU r'.sub.k,m/m' =h.sub.m'.sup.t (k-1) s.sub.m/m' (k) (10)
Then, the branch metric b.sub.k,m/m' for this branch m/m' can be calculated as a square of an absolute value of a difference between the estimated received signal r'.sub.k,m/m' and the actual received signal r.sub.k, by the following equation (11). ##EQU3##
Also, the path metric p.sub.k,m for this branch m/m' defined as a cumulative value of the branch metrics can be calculated by the following equation (12), using each branch metric calculated according to the equation (11) and the path metric for the previous state m'(k-1). EQU p.sub.k,m =p.sub.k-1,m' +b.sub.k,m/m' ( 12)
Then, one branch among the Q different branches reaching to the state m(k) which minimizes the path metric calculated according to the equation (12) is selected by the processing control unit 16, such that the new survivor path for the state m(k) can be obtained by adding the selected branch at the end of the previous survivor path for the previous state m'(k-1).
The obtained survivor path and the path metric for this survivor path are then stored together in the path memory 13.
This procedure is also carried out for each state m(k), so as to update all the survivor paths and the path metrics for all the states at the time kT, and then k is increased by one to proceed to the next time.
Thus, the procedure of this conventional method of maximum likelihood sequence estimation described above can be represented by a diagram shown in FIG. 3.
More specifically, for a given set of the received signals {r.sub.k }, a received signal vector r(k-1) is read out from the received signal memory 12 at the step S11, while each transmission sequence candidate is specified according to the updated survivor path read out from the path memory 13 at the step S12 and the matrix G.sub.m' (k-1) for the specified transmission sequence candidate is read out from the matrix memory 11 at the step S13. Then, a matrix calculation to obtain the estimated transmission path response h.sub.m' (k-1) from the received signal vector r(k-1) read out at the step S11 and the matrix G.sub.m' (k-1) read out at the step S13 is carried out at the step S14, and an inner product calculation to obtain the estimated received signal r'.sub.k,m/m' from the estimated transmission path response h.sub.m' (k-1) calculated at the step S14 and the transmission signal s.sub.m/m' (k) for the branch m/m' in the transmission sequence candidate specified at the step S12 is carried out at the step S15. Then, a difference between each received signal r.sub.k and the estimated received signal r'.sub.k,m/m' is calculated at the step S16, and the branch metric is calculated at the step S17 from the difference calculated at the step S16. Finally, the survivor path is selected at the step S18 according to the branch metric calculated at the step S17, such that the survivor path and the path metric in the path memory 13 can be updated at the step S12.
When this procedure is continued for each time k and the survivor paths are traced backwards in time (toward the left in the trellis of FIG. 2), the number of the survivor paths gradually decreases and the survivor paths eventually merge into only one survivor path at some point in the past, so that the estimation of the transmission sequence can be regarded as completed up to that point at which the survivor paths merge. Thus, by repeating the updating of the survivor paths and the transmission path response estimation alternately, the transmission signal sequence can be estimated sequentially, with some time lag.
In this method, the superior high speed follow up characteristic is realizable because the transmission path response estimation is made on a basis of a finite number (equal to NT) of the received signals. Here, the follow up characteristic can be improved by making N smaller. However, in order to reduce the influence of the noises, a larger N is preferable. Consequently, in practice, the size of N is determined according to the relative importance of the follow up characteristic and the noise influence reduction.
Now, this conventional method for the adaptive maximum likelihood sequence estimation scheme has been associated with the problem concerning the huge amount of real time calculations required.
Namely, the amount of real time calculations required per each sampling time can be expressed as (amount of calculations per branch).times.(number of branches per state).times.(number of states). Here, the last two factors are unaffected by the branch metric calculation procedure adopted, once the trellis is specified, so that the total amount of real time calculations required basically depends on how large the amount of calculations per branch is.
In this regard, the majority of the amount of calculations per branch is occupied by the calculations of the estimated transmission path response h.sub.m' (k-1) and the calculations for deriving the estimated received signal r'.sub.k,m/m' from the estimated transmission path response.
More specifically, the calculations of the estimated transmission path response require LN steps of multiplication and L(N-1) steps of addition, while the calculations of the estimated received signal require L steps of multiplication and (L-1) steps of addition. Besides these, the calculation of the path metric also requires one step of subtraction and one step of square calculation, so that the total number of these real time calculations required in the conventional method is (2LN+L+1), irrespective of the difference in types of calculations.
This number of real time calculations required can be particularly large for a case L must be set to be large, such as a case in which the multi-path delay extends over several symbols, and could present a serious problem in practice.